package Stack;

import java.util.Stack;

public class _739_DailyTemperatures {
    //brute force solution
    public int[] dailyTemperatures0(int[] temperatures) {
            int[] count = new int[temperatures.length];
        for(int i=temperatures.length-1;i>=0;i--) {
            int tempCount = 0;
            boolean warmer = false;
            for(int j=i+1;j<temperatures.length;j++) {
                if (temperatures[i] >= temperatures[j]) {
                    tempCount++;
                } else {
                    warmer = true;
                    tempCount++;
                    break;
                }
            }
            if (warmer) {
                count[i] = tempCount;
            } else {
                count[i] = 0;
            }
        }
        return count;
    }

    //reference solution,use stack
    //hint:only store the bigger list like [2,3,5] which related to [73,74,78],and compare the current
    //value with stack's value and get the length
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Stack<Integer> stack = new Stack();
        for(int i=temperatures.length-1;i>=0;i--) {
            while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
                stack.pop();
            }
            result[i] = stack.isEmpty()?0:(stack.peek()-i);
            stack.push(i);
        }
        return result;
    }
}
